package com.atguigu.tree;


import java.util.*;

/**
 * 节点存储二叉树
 * 二叉树：每个节点最多只能有两个子节点的一种形式
 * 满二叉树: 二叉树的叶子节点都在最后一层，并且满足节点数=2^n-1(n:层数)
 * 完全二叉树：二叉树的叶子节点都在最后一层或者倒数第二层，且最后一层在左边连续，倒数第二层从右边开始连续
 * 二叉树的遍历：
 * 前序遍历： 根左右
 * 中序遍历: 左根右
 * 后序遍历: 左右根
 * 二叉树的查找:
 * 前序查询
 * 中序查询
 * 后序查询
 * 删除节点及其子节点
 * 删除叶子节点: 删除节点
 * 删除非叶子节点: 删除该子树
 * 线索二叉树：
 * 对于n个节点的二叉树在存储的二叉链中存在n+1个空链域，
 * 中序线索二叉树（TODO 没有理解）
 * 最优二叉树(哈夫曼树)：
 * 由n个带权值的叶子节点构成的二叉树,权值大的离根节点更近
 * 二叉排序树（BST）
 * 任何一个非叶子节点要求左子节点的值小于当前节点的值，右子节点的值要求大于当前子节点饿值,
 * 如果有相同的值,可以将改节点放在左子节点或者右子节点
 * 平衡二叉树(AVL)
 * 一颗空树或者左右子树的高度的绝对值不超过1,并且左右子树也是一颗平衡二叉树
 * B树和B+树
 * B树:
 * B+树： 所有节点得数据都放在叶子节点、所有得关键字都在叶子节点得链表中且关键字都是有序得、不可能在非叶子节点命中、非叶子节点相当于叶子节点得索引、适合文件索引系统
 *
 * @author dataexa
 * @Date 2023/12/27
 */
public class NodeTreeTest {
    public static void main(String[] args) {
        TreeNode root = new TreeNode("1");
        TreeNode node1 = new TreeNode("2-1");
        TreeNode node2 = new TreeNode("2-2");
        TreeNode node3 = new TreeNode("3-1");
        TreeNode node4 = new TreeNode("3-3");
        TreeNode node5 = new TreeNode("4-1");
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node2.left = node4;
        node3.right = node5;
//        preOrder(root);
//        TreeNode node = realSearch(root, "2-1");
        System.out.println("删除前前序遍历: ");
        preOrder(root);
        String value = "4-1";
        if (root != null) {
            // 如果只有一个root，并且是要删除的
            if (value.equals(root.name)) {
                root = null;
            } else {
                deleteNode(root, value);
            }
        }
        System.out.println("删除后前序遍历: ");
        preOrder(root);
        System.out.println("========执行完成===========");
    }
    //==========================遍历===================================//

    /**
     * 前序遍历 ： 根左右
     *
     * @param node
     */
    public static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        if (node.left != null) {
            preOrder(node.left);
        }
        if (node.right != null) {
            preOrder(node.right);
        }
    }

    /**
     * 中序遍历
     * 坐跟右
     *
     * @param treeNode
     */
    public static void midOrder(TreeNode treeNode) {
        if (treeNode.left != null) {
            midOrder(treeNode.left);
        }
        System.out.println(treeNode);
        if (treeNode.right != null) {
            midOrder(treeNode.right);
        }
    }

    /**
     * 后序遍历
     * 左右根
     *
     * @param treeNode
     */
    public static void realOrder(TreeNode treeNode) {
        if (treeNode.left != null) {
            realOrder(treeNode.left);
        }
        if (treeNode.right != null) {
            realOrder(treeNode.right);
        }
        System.out.println(treeNode);
    }


    //==========================查询===================================//

    /**
     * 前序查询
     *
     * @param value
     * @return
     */
    public static TreeNode preSearch(TreeNode treeNode, String value) {
        if (value.equals(treeNode.name)) {
            return treeNode;
        }
        TreeNode node = null;
        if (treeNode.left != null) {
            node = preSearch(treeNode.left, value);
        }
        if (node != null) {
            return node;
        }
        if (treeNode.right != null) {
            node = preSearch(treeNode.right, value);
        }
        return node;
    }

    /**
     * 中序查找
     * 左根右
     *
     * @param treeNode
     * @param value
     * @return
     */
    public static TreeNode midSearch(TreeNode treeNode, String value) {
        TreeNode node = null;
        if (treeNode.left != null) {
            node = midSearch(treeNode.left, value);
        }
        if (node != null) {
            return node;
        }
        System.out.println(treeNode);
        if (value.equals(treeNode.name)) {
            return treeNode;
        }
        if (treeNode.right != null) {
            node = midSearch(treeNode.right, value);
        }
        return node;
    }

    /**
     * 后序查询
     * 左右根
     *
     * @param treeNode
     * @param value
     * @return
     */
    public static TreeNode realSearch(TreeNode treeNode, String value) {
        TreeNode node = null;
        if (treeNode.left != null) {
            node = realSearch(treeNode.left, value);
        }
        if (node != null) {
            return node;
        }
        if (treeNode.right != null) {
            node = realSearch(treeNode.right, value);
        }
        if (node != null) {
            return node;
        }
        if (value.equals(treeNode.name)) {
            return treeNode;
        }
        return node;
    }

    //==========================删除===================================//

    /**
     * 删除节点及其子节点
     * 判断待删除的节点是当前节点的子节点
     *
     * @param treeNode
     * @param value
     */
    public static void deleteNode(TreeNode treeNode, String value) {
        // 左子树置空
        if (treeNode.left != null && value.equals(treeNode.left.name)) {
            treeNode.left = null;
            return;
        }
        // 右子树置空
        if (treeNode.right != null && value.equals(treeNode.right.name)) {
            treeNode.right = null;
            return;
        }
        // 左子树递归
        if (treeNode.left != null) {
            deleteNode(treeNode.left, value);
        }
        // 右子树递归
        if (treeNode.right != null) {
            deleteNode(treeNode.right, value);
        }
    }

    /**
     * 中序遍历线索二叉树
     * left：可能是前驱或者左子节点
     * right: 可能是后继或者有子节点
     */
    public static void midThreadNode(TreeNode2 treeNode2) {
        if (treeNode2 == null) {
            return;
        }
        TreeNode2 pre = null;
        // 线索化左子树
        if (treeNode2.left != null) {
            pre = treeNode2;
            midThreadNode(treeNode2.left);
        }
        // 线索化当前节点
        if (treeNode2.left == null) {
            // 当前节点做指针指向前驱节点
            treeNode2.left = pre;
            treeNode2.leftType = 1;
        }
        // 处理后继节点
        if (pre != null && pre.right == null) {
            pre.right = treeNode2;
            pre.rightType = 1;
        }
        // 每处理一个节点后，让当前节点的下一个节点是上一个节点的前驱节点

        // 线索化右子树
        if (treeNode2.right != null) {
            midThreadNode(treeNode2.right);
        }
    }

    //==========================赫夫曼树===================================//

    /**
     * 创建哈夫曼树
     */
    private static HuffManTreeNode createHuffmanTree(int[] arr) {
        List<HuffManTreeNode> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new HuffManTreeNode(value));
        }

        while (nodes.size() > 1) {
            // 进行排序
            Collections.sort(nodes);
            HuffManTreeNode leftNode = nodes.get(0);
            HuffManTreeNode rightNode = nodes.get(1);
            // 构建一个新的节点
            HuffManTreeNode parent = new HuffManTreeNode(leftNode.value + rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;
            // 从arrayList中删除处理过的二叉树
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将parent加入nodes
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    /**
     * 更具数据和权重构建赫夫曼树
     *
     * @param bytes
     * @return
     */
    private static Node createHuffmanTreeByWeight(byte[] bytes) {
        List<Node> nodes = new ArrayList<>();
        Map<Byte, Integer> map = new HashMap<>();
        for (byte aByte : bytes) {
            if (map.containsKey(aByte)) {
                Integer count = map.get(aByte);
                map.put(aByte, count + 1);
            } else {
                map.put(aByte, 1);
            }
        }
        // 将map的每个键值对转成一个Node对象并加入nodes集合
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        while (nodes.size() > 1) {
            // 排序从小到大
            Collections.sort(nodes);
            // 取出第一颗最小的二叉树
            Node leftNode = nodes.get(0);
            // 取出第二颗最小的二叉树
            Node rightNode = nodes.get(1);
            // 创建一颗新的二叉树，它没有根节点，只有权值
            Node parent = new Node(null, leftNode.weight + rightNode.weight);
            parent.left = leftNode;
            parent.right = rightNode;
            // 将已经处理的两颗二叉树从nodes移除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 将新的二叉树加入nodes
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //==========================二叉排序树===================================//

    /**
     * 创建一个二叉排序树
     *
     * @param root
     * @param treeNode
     */
    private static void createBinarySortTree(TreeNode root, TreeNode treeNode) {
        if (root == null) {
            root = treeNode;
        } else {
            addBinarySortTree(root, treeNode);
        }
    }

    /**
     * 添加节点
     *
     * @param root
     * @param treeNode
     */
    public static void addBinarySortTree(TreeNode root, TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        // 如果需要添加的节点小于当前节点的值
        if (treeNode.value < root.value) {
            // 如果左节点为空，直接挂在左节点
            if (root.left == null) {
                root.left = treeNode;
            } else {
                // 递归的向左子节点添加
                addBinarySortTree(root.left, treeNode);
            }
        } else {
            if (root.right == null) {
                root.right = treeNode;
            } else {
                addBinarySortTree(root.right, treeNode);
            }
        }
    }


}

// 哈夫曼树（需要从小到大排序）
class HuffManTreeNode implements Comparable<HuffManTreeNode> {
    int value; // 节点的权值
    HuffManTreeNode left;
    HuffManTreeNode right;

    public HuffManTreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "HuffManTreeNode{" + "value='" + value + '\'' + '}';
    }

    @Override
    public int compareTo(HuffManTreeNode o) {
        // 表示从小到大排序
        return this.value - o.value;
    }
}

// 创建赫夫曼树带数据和权值
class Node implements Comparable<Node> {
    Byte data; // 存放数据的字符
    int weight;  // 表示字符出现的次数
    Node left;
    Node right;

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Node{" + "data=" + data + ", weight=" + weight + '}';
    }
}

// 普通二叉树
class TreeNode {
    String name;
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

    public TreeNode(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode{" + "name='" + name + '\'' + '}';
    }
}

// 线索二叉树
class TreeNode2 {
    String name;
    TreeNode2 left;
    TreeNode2 right;
    // 如果leftType==0表示指向的是左子树，==1表示指向的是前驱节点
    int leftType;
    // 如果rightType==0表示指向的是右子树，==1表示指向的是后继节点
    int rightType;

    public TreeNode2(String name) {
        this.name = name;
    }

    @Override
    public String toString() {
        return "TreeNode2{" + "name='" + name + '\'' + '}';
    }
}
